package com.jwetherell.my.problems.misc;

import java.util.ArrayList;
import java.util.List;

class PrintUniqueRowsOfAMatrix {

	List<Node> trees = new ArrayList<Node>();

	public static void main(String[] args) {

		int[][] input = new int[][] { { 1, 0 }, { 1, 0 }, { 1, 0 }, { 1, 1 },
				{ 1, 1 } };
		
		PrintUniqueRowsOfAMatrix sol = new PrintUniqueRowsOfAMatrix();
		sol.printUniqueRows(input);

	}

	public void printUniqueRows(int[][] input) {

		List<Node> trees = populateTrees(input);

		if (!trees.isEmpty()) {
			for (Node tree : trees) {
				printTree(tree, "");
			}
		}

	}

	public List<Node> populateTrees(int[][] input) {

		for (int i = 0; i < input.length; i++) {
			Node node = null;
			for (int j = 0; j < input[0].length; j++) {
				if (j == 0) {
					node = getTree(input[i][j]);
					continue;
				}

				if (node.left != null) {
					if (node.left.data == input[i][j]) {
						node = node.left;
						continue;
					} else if (node.right != null) {
						// not checking the data equality because it has to
						// match because only two values are possible i.e. 0 or
						// 1
						node = node.right;
						continue;
					} else {
						node.right = new Node(input[i][j]);
						node = node.right;
						continue;
					}

				} else {
					node.left = new Node(input[i][j]);
					node = node.left;
					continue;
				}

			}
		}

		return trees;
	}

	public void printTree(Node tree, String prefix) {
		
		if (tree.left == null) {
			System.out.print(prefix);
			System.out.println(tree.data + " ");
		}

		prefix += tree.data;
		if (tree.left != null)
			printTree(tree.left, prefix);

		if (tree.right != null)
			printTree(tree.right, prefix);
	}

	public Node getTree(int i) {

		if (!trees.isEmpty()) {
			for (Node root : trees) {
				if (root.data == i)
					return root;
			}
		}

		Node node = new Node(i);
		trees.add(node);
		return node;
	}

	static class Node {
		public Node left;
		public Node right;
		public int data;

		public Node(int i) {
			this.data = i;
		}
	}
}